type Fn = (...args: any[]) => any
interface TreeHelperConfig {
  id: string
  pid: string
  children: string
  callback: Fn
  fullNameSplit: string
}
const DEFAULT_CONFIG: TreeHelperConfig = {
  id: 'id',
  pid: 'pId',
  children: 'children',
  callback: () => {},
  fullNameSplit: '/'
}

const getConfig = (config: Partial<TreeHelperConfig>) => Object.assign({}, DEFAULT_CONFIG, config)

/**
 * 将列表转换为树形结构
 * @param list 列表数据
 * @param config
 * @returns
 */
export function listToTree<T = any>(list?: any[], config: Partial<TreeHelperConfig> = {}): T[] {
  // 获取配置
  const conf = getConfig(config) as TreeHelperConfig
  // 创建一个Map，用于存储节点
  const nodeMap = new Map()
  // 创建一个空数组，用于存储结果
  const result: T[] = []
  // 获取配置中的id、pid、children、fullNameSplit属性
  const { id, pid, children, fullNameSplit } = conf

  // 遍历列表，将每个节点存储到Map中
  for (const node of list || []) {
    node[children] = node[children] || []
    nodeMap.set(node[id], node)
  }
  // 再次遍历列表，将节点添加到父节点的children数组中
  for (const node of list || []) {
    const parent = nodeMap.get(node[pid])
    ;(parent ? parent[children] : result).push(node)
    // 如果节点有name属性，则添加_fullName属性
    if (node.name) {
      node._name = node.name
      if (parent && parent._fullName) {
        node._fullName = parent._fullName + fullNameSplit + node._name
      } else {
        node._fullName = node._name
      }
    }
    // 执行回调函数
    conf.callback(parent, node)
  }
  // 返回结果
  return result
}

// 将树形结构转换为列表结构
export function treeToList<T = any>(tree: any, config: Partial<TreeHelperConfig> = {}): T {
  // 获取配置
  config = getConfig(config)
  // 获取子节点的字段名
  const { children } = config
  // 将树形结构转换为列表结构
  const result: any = [...tree]
  // 遍历列表
  for (let i = 0; i < result.length; i++) {
    // 如果当前节点没有子节点，则跳过
    if (!result[i][children!]) continue
    // 将子节点插入到当前节点之后
    result.splice(i + 1, 0, ...result[i][children!])
  }
  // 返回列表结构
  return result
}

// 导出一个函数，用于在树形结构中查找节点
export function findNode<T = any>(
  // 树形结构
  tree: any,
  // 查找节点的函数
  func: Fn,
  // 配置项
  config: Partial<TreeHelperConfig> = {}
): T | null {
  // 获取配置项
  config = getConfig(config)
  // 获取子节点的键名
  const { children } = config
  // 将树形结构转换为数组
  const list = [...tree]
  // 遍历数组
  for (const node of list) {
    // 如果节点满足条件，则返回该节点
    if (func(node)) return node
    // 如果节点有子节点，则将子节点加入数组
    node[children!] && list.push(...node[children!])
  }
  // 如果没有找到满足条件的节点，则返回null
  return null
}

// 导出一个函数，用于在树形结构中查找所有符合条件的节点
export function findNodeAll<T = any>(
  // 树形结构
  tree: any,
  // 判断节点是否符合条件的函数
  func: Fn,
  // 配置项
  config: Partial<TreeHelperConfig> = {}
): T[] {
  // 获取配置项
  config = getConfig(config)
  // 获取子节点的字段名
  const { children } = config
  // 将树形结构转换为数组
  const list = [...tree]
  // 存储符合条件的节点
  const result: T[] = []
  // 遍历数组
  for (const node of list) {
    // 如果节点符合条件，则将其添加到结果数组中
    func(node) && result.push(node)
    // 如果节点有子节点，则将子节点添加到数组中
    node[children!] && list.push(...node[children!])
  }
  // 返回结果数组
  return result
}

// 导出一个函数，用于在树结构中查找路径
export function findPath<T = any>(
  // 树结构
  tree: any,
  // 回调函数，用于判断节点是否满足条件
  func: Fn,
  // 配置项，用于指定子节点的属性名
  config: Partial<TreeHelperConfig> = {}
): T | T[] | null {
  // 获取配置项
  config = getConfig(config)
  // 用于存储路径的数组
  const path: T[] = []
  // 用于存储待遍历的节点列表
  const list = [...tree]
  // 用于存储已遍历的节点
  const visitedSet = new Set()
  // 获取子节点的属性名
  const { children } = config
  // 遍历节点列表
  while (list.length) {
    // 获取当前节点
    const node = list[0]
    // 如果当前节点已遍历过，则从路径中移除，并从待遍历列表中移除
    if (visitedSet.has(node)) {
      path.pop()
      list.shift()
    } else {
      // 将当前节点标记为已遍历
      visitedSet.add(node)
      // 如果当前节点有子节点，则将子节点添加到待遍历列表中
      node[children!] && list.unshift(...node[children!])
      // 将当前节点添加到路径中
      path.push(node)
      // 如果当前节点满足条件，则返回路径
      if (func(node)) {
        return path
      }
    }
  }
  // 如果遍历完所有节点仍未找到满足条件的节点，则返回null
  return null
}

// 导出一个函数，用于查找树中所有满足条件的路径
export function findPathAll(tree: any, func: Fn, config: Partial<TreeHelperConfig> = {}) {
  // 获取配置
  config = getConfig(config)
  // 定义一个空数组，用于存储路径
  const path: any[] = []
  // 将树展开为一个数组
  const list = [...tree]
  // 定义一个空数组，用于存储满足条件的路径
  const result: any[] = []
  // 定义一个集合，用于存储已经访问过的节点
  const visitedSet = new Set(),
    { children } = config
  // 当数组不为空时，循环执行
  while (list.length) {
    // 获取数组的第一个节点
    const node = list[0]
    // 如果节点已经访问过，则将路径和节点从数组中移除
    if (visitedSet.has(node)) {
      path.pop()
      list.shift()
    } else {
      // 否则，将节点添加到集合中
      visitedSet.add(node)
      // 如果节点有子节点，则将子节点添加到数组中
      node[children!] && list.unshift(...node[children!])
      // 将节点添加到路径中
      path.push(node)
      // 如果节点满足条件，则将路径添加到结果数组中
      func(node) && result.push([...path])
    }
  }
  // 返回结果数组
  return result
}

// 导出一个函数，用于过滤树形结构的数据
export function filter<T = any>(
  // 树形结构的数据
  tree: T[],
  // 过滤函数，接收一个节点，返回一个布尔值
  func: (n: T) => boolean,
  // 配置项，默认为空对象
  config: Partial<TreeHelperConfig> = {},
  // 只搜索某一层的节点，默认为undefined
  onlySearchLevel?: number
): T[] {
  // 获取配置项
  config = getConfig(config)
  // 获取子节点的字段名
  const children = config.children as string
  // 定义一个递归函数，用于过滤节点
  function listFilter(list: T[], level?: number) {
    // 遍历节点列表
    return list
      .map((node: any) => ({ ...node }))
      .filter((node) => {
        // 如果当前层级为1，直接调用过滤函数
        if (level === 1) {
          return func(node)
        }
        // 如果只搜索某一层，且当前层级不为空，则递归过滤子节点
        if (onlySearchLevel && level) {
          node[children] = node[children] && listFilter(node[children], level - 1)
          // 如果子节点存在且长度大于0，则返回true
          return node[children] && node[children].length
        }
        // 否则，递归过滤子节点
        node[children] = node[children] && listFilter(node[children])
        // 如果当前节点满足过滤函数，或者子节点存在且长度大于0，则返回true
        return func(node) || (node[children] && node[children].length)
      })
  }
  // 调用递归函数，返回过滤后的结果
  return listFilter(tree, onlySearchLevel)
}

// 遍历树形结构
export function forEach<T = any>(
  // 树形结构数组
  tree: T[],
  // 遍历函数
  func: (n: T) => any,
  // 配置项
  config: Partial<TreeHelperConfig> = {}
): void {
  // 获取配置项
  config = getConfig(config)
  // 将树形结构数组转换为数组
  const list: any[] = [...tree]
  // 获取配置项中的children字段
  const { children } = config
  // 遍历数组
  for (let i = 0; i < list.length; i++) {
    //func 返回true就终止遍历，避免大量节点场景下无意义循环，引起浏览器卡顿
    if (func(list[i])) {
      return
    }
    children && list[i][children] && list.splice(i + 1, 0, ...list[i][children])
  }
}

/**
 * @description: Extract tree specified structure
 */
export function treeMap<T = any>(treeData: T[], opt: { children?: string; conversion: Fn }): T[] {
  return treeData.map((item) => treeMapEach(item, opt))
}

/**
 * @description: Extract tree specified structure
 */
// 导出一个函数treeMapEach，用于遍历树形结构的数据
export function treeMapEach(
  // data为要遍历的数据，类型为any
  data: any,
  // options为可选参数，包含children和conversion两个属性
  { children = 'children', conversion }: { children?: string; conversion: Fn }
) {
  // 判断data中是否存在children属性，并且children属性是否为数组且长度大于0
  const haveChildren = Array.isArray(data[children]) && data[children].length > 0
  // 调用conversion函数，将data作为参数传入，并将返回值赋给conversionData
  const conversionData = conversion(data) || {}
  // 如果存在children属性，则递归调用treeMapEach函数，遍历children属性中的每一个元素
  if (haveChildren) {
    return {
      // 将conversionData和children属性中的每一个元素递归调用treeMapEach函数后的结果合并
      ...conversionData,
      [children]: data[children].map((i: number) =>
        treeMapEach(i, {
          children,
          conversion
        })
      )
    }
  } else {
    // 如果不存在children属性，则直接返回conversionData
    return {
      ...conversionData
    }
  }
}

/**
 * 递归遍历树结构
 * @param treeDatas 树
 * @param callBack 回调
 * @param parentNode 父节点
 */
export function eachTree(treeDatas: any[], callBack: Fn, parentNode = {}) {
  treeDatas.forEach((element) => {
    const newNode = callBack(element, parentNode) || element
    if (element.children) {
      eachTree(element.children, callBack, newNode)
    }
  })
}
